
//1. 排序 然后二分
function search(nums: number[], target: number): number {
    if(!nums || nums.length===0){
        return -1;
    }
    if(nums.length === 1){
        return nums[0] === target ? 0: -1;
    }
    // sort
    let left:number = 0;
    let right:number = nums.length -1;
    while(left < right){
        let mid:number =Math.floor((left+right)/2)
        if()
    }
};


// 2. 直接二分查找
function search1(nums: number[], target: number): number {
    if(!nums || nums.length===0){
        return -1;
    }
    if(nums.length === 1){
        return nums[0] === target ? 0: -1;
    }
    let left:number = 0;
    let right:number =nums.length -1;

    while(left <= right){
        let mid = Math.floor((left+right)/2)
        if(nums[mid] === target){
            return mid;
        }
        // nums[0] <= nums[mid] 表明 从left-->mid-1内数组是升序
        if(nums[0] <= nums[mid]){
            // 如果 nums[mid]>target >= nums[0] 则表明 target 在 left -> mid-1 的区间内
            // 可以 想左收敛
            if(nums[mid]>target && target >= nums[0]){
                right = mid-1;
            // 如果target不在 left ->mid-1的区间里面，
            // 则 想 右边收敛
            }else {
                left = mid +1;
            }
            
        // nums[0] > nums[mid] 表明mid--->right 是升序的
        } else {
            // nums[nums.length -1] >= target > nums[mid] 表明target 在 mid -->right的区间内，
            // 则向右收敛
            if(nums[nums.length -1] >= target && target > nums[mid]){
                left = mid +1;
            // 表明target 不在 mid -->right的区间内，
            // 向左收敛
            }else {
                right = mid -1;
            }
        }

    }
    return -1;

};

// 2. 直接二分查找
function search2(nums: number[], target: number): number {
    if(!nums || nums.length===0){
        return -1;
    }
    if(nums.length === 1){
        return nums[0] === target ? 0: -1;
    }
    let left:number = 0;
    let right:number =nums.length -1;

    while(left <= right){
        let mid = Math.floor((left+right)/2)
        if(nums[mid] === target){
            return mid;
        }
        if(nums[mid] > target){
            
        }
        // nums[0] <= nums[mid] 表明 从left-->mid-1内数组是升序
        if(nums[0] <= nums[mid]){
            // 如果 nums[mid]>target >= nums[0] 则表明 target 在 left -> mid-1 的区间内
            // 可以 想左收敛
            if(nums[mid]>target && target >= nums[0]){
                right = mid-1;
            // 如果target不在 left ->mid-1的区间里面，
            // 则 想 右边收敛
            }else {
                left = mid +1;
            }
            
        // nums[0] > nums[mid] 表明mid--->right 是升序的
        } else {
            // nums[nums.length -1] >= target > nums[mid] 表明target 在 mid -->right的区间内，
            // 则向右收敛
            if(nums[nums.length -1] >= target && target > nums[mid]){
                left = mid +1;
            // 表明target 不在 mid -->right的区间内，
            // 向左收敛
            }else {
                right = mid -1;
            }
        }

    }
    return -1;

};
